#include <iostream>
#include <stack>

using namespace std;
// 20. 有效的括号
// 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

class Solution {
public:
    bool isValid(string s) {
        stack<char> st; // 定义一个栈容器st
        size_t n = s.size();  // 求字符串的长度n

        for(int i = 0; i < n; i++)
        {
            if(s[i] == '(' || s[i] == '[' || s[i] == '{')
                st.push(s[i]);    // 所有左括号进栈
            else {
                if(st.empty()) // 栈空时返回false
                    return false;

                char e = st.top();   // 取栈顶元素
                if(s[i] == ')')
                {
                    if(e != '(')    // 不配对
                        return false;
                    else
                        st.pop();   // 出栈，继续匹配
                }
                else if(s[i] == ']')
                {
                    if(e != '[')
                        return false;
                    else
                        st.pop();
                }
                else if(s[i] == '}')
                {
                    if(e != '{')
                        return false;
                    else
                        st.pop();
                }
            }
        }

        if(!st.empty()) // 栈不空返回false
            return false;
        else
            return true;
    }
};
int main() {
    cout << boolalpha << Solution().isValid("()")<<endl;
    cout << boolalpha << Solution().isValid("()[]{}")<<endl;
    cout << boolalpha << Solution().isValid("(]")<<endl;

    return 0;
}
